import java.util.*;

// 力扣399. 除法求值
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 1. 构建图
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);

        // 2. 处理查询
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);
            results[i] = getPathValue(graph, start, end, new HashSet<>());
        }
        return results;
    }

    // 构建图结构
    private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String u = equations.get(i).get(0);
            String v = equations.get(i).get(1);
            double value = values[i];

            // 添加正向边 u->v
            graph.putIfAbsent(u, new HashMap<>());
            graph.get(u).put(v, value);

            // 添加反向边 v->u
            graph.putIfAbsent(v, new HashMap<>());
            graph.get(v).put(u, 1.0 / value);
        }

        return graph;
    }

    // DFS查找路径值
    private double getPathValue(Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited) {
        // 节点不存在
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            return -1.0;
        }

        // 到达目标节点
        if (start.equals(end)) {
            return 1.0;
        }

        visited.add(start);

        // 遍历邻居
        for (Map.Entry<String, Double> neighbor : graph.get(start).entrySet()) {
            String next = neighbor.getKey();
            if (visited.contains(next)) continue; // 说明此时 a - > b and b - > a 是同一个equation

            // 当能找到问题的答案的时候 next等于end 然后返回1.0
            double product = getPathValue(graph, next, end, visited);
            if (product != -1.0) {
                return neighbor.getValue() * product;
            }
        }

        visited.remove(start);
        return -1.0;
    }
}



// 力扣909. 蛇梯棋
class Solution1 {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;  // 终点编号

        // 将二维棋盘转换为一维数组，moves[1]到moves[n²]存储每个格子的值
        int[] moves = new int[target + 1];
        boolean[] visited = new boolean[target + 1]; // 记录已访问的格子

        // 预处理：将蛇形棋盘转换为线性数组
        int index = 1;
        boolean reverse = false; // 标记当前行是否需要反向遍历
        for (int i = n - 1; i >= 0; i--) { // 从最后一行开始
            if (!reverse) {
                // 从左到右遍历
                for (int j = 0; j < n; j++) {
                    moves[index++] = board[i][j];
                }
            } else {
                // 从右到左遍历
                for (int j = n - 1; j >= 0; j--) {
                    moves[index++] = board[i][j];
                }
            }
            reverse = !reverse; // 切换下一行的遍历方向
        }

        // BFS队列初始化
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);  // 从起点1开始
        visited[1] = true;
        int steps = 0;    // 记录掷骰次数

        while (!queue.isEmpty()) {
            int size = queue.size();
            // 处理当前层的所有可能位置
            for (int i = 0; i < size; i++) {
                int current = queue.poll();

                // 到达终点
                if (current == target) {
                    return steps;
                }

                // 模拟掷骰子(1-6)
                for (int j = 1; j <= 6; j++) {
                    int next = current + j;

                    // 超出终点则停止
                    if (next > target) {
                        break;
                    }

                    // 检查是否有蛇或梯子
                    if (moves[next] != -1) {
                        next = moves[next]; // 跳转到目标位置
                    }

                    // 如果新位置未访问过，加入队列
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
            steps++; // 每处理完一层，步数+1
        }

        // 无法到达终点
        return -1;
    }
}